<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>ACM笔记 | Mox的笔记库</title><meta name="keywords" content="Working"><meta name="author" content="MocusEZ"><meta name="copyright" content="MocusEZ"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="由于个人时间紧迫，外加阅读书目改变，本笔记不再更新">
<meta property="og:type" content="article">
<meta property="og:title" content="ACM笔记">
<meta property="og:url" content="https://www.mocusez.site/posts/6db3.html">
<meta property="og:site_name" content="Mox的笔记库">
<meta property="og:description" content="由于个人时间紧迫，外加阅读书目改变，本笔记不再更新">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://ss0.bdstatic.com/70cFvHSh_Q1YnxGkpoWK1HF6hhy/it/u=4088345299,2353129269&fm=26&gp=0.jpg">
<meta property="article:published_time" content="2020-11-22T03:42:51.000Z">
<meta property="article:modified_time" content="2021-02-19T06:20:51.000Z">
<meta property="article:author" content="MocusEZ">
<meta property="article:tag" content="Working">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://ss0.bdstatic.com/70cFvHSh_Q1YnxGkpoWK1HF6hhy/it/u=4088345299,2353129269&fm=26&gp=0.jpg"><link rel="shortcut icon" href="/img/title.jpg"><link rel="canonical" href="https://www.mocusez.site/posts/6db3"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//hm.baidu.com"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.min.css" media="print" onload="this.media='all'"><script>var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?c85c9eaebc158345532b86397a6dded9";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: {"path":"/search.xml","preload":false,"languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'ACM笔记',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-02-19 14:20:51'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><meta name="generator" content="Hexo 6.2.0"><link rel="alternate" href="/atom.xml" title="Mox的笔记库" type="application/atom+xml">
</head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/head.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">61</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">8</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链&amp;私人收藏</span></a></div><div class="menus_item"><a class="site-page" href="/board/"><i class="fa-fw fas fa-user"></i><span> 留言板</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://ss0.bdstatic.com/70cFvHSh_Q1YnxGkpoWK1HF6hhy/it/u=4088345299,2353129269&amp;fm=26&amp;gp=0.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">Mox的笔记库</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链&amp;私人收藏</span></a></div><div class="menus_item"><a class="site-page" href="/board/"><i class="fa-fw fas fa-user"></i><span> 留言板</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">ACM笔记</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-11-22T03:42:51.000Z" title="发表于 2020-11-22 11:42:51">2020-11-22</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-02-19T06:20:51.000Z" title="更新于 2021-02-19 14:20:51">2021-02-19</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%97%A5%E5%B8%B8%E7%AC%94%E8%AE%B0/">日常笔记</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="ACM笔记"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>干ACM了，emmm(持续更新中)</p>
<p>2021年2月28日：由于个人时间紧迫，外加阅读书目改变，本笔记不再更新</p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://imgchr.com/i/D8CZBF"><img src="https://s3.ax1x.com/2020/11/22/D8CZBF.jpg" alt="D8CZBF.jpg"></a></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">C++通用库，使c++支持所有库，vj要选c++5.1.0/g++才行</span><br></pre></td></tr></table></figure>

<p>按照《算法竞赛:入门到进阶》编排内容</p>
<p>ACM (Advanced Computer Maker)</p>
<p>想要编写又快又好的程序，构造测试数据和写出优良代码一样重要</p>
<h2 id="环境配置"><a href="#环境配置" class="headerlink" title="环境配置"></a>环境配置</h2><p>谁叫这是官配IDE，不然怎么会用这种东西</p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/liu_feng_zi_/article/details/84634212">CodeBlocks17.12版本无法进行单步调试的相关原因及可能的解决办法</a></p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/oh_lala/article/details/88996898">CodeBlock无法断点调试的解决方案</a></p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/autocyz/article/details/42368147">在codeblocks中使用C++11标准，安装及配置方法_autocyz-CSDN博客</a></p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/lydyangliu/article/details/9312757">codeblocks 字体光标颜色设置_lydcsdn-CSDN博客</a></p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/wretchedme/article/details/40663471">codeblocks 背景设置和光标的设置！！！_谈笑风声，雨下成林-CSDN博客</a></p>
<p>2020年11月23日，我的codeblock出现编译完的程序死锁，使用完居然不自动释放，垃圾东西</p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://imgchr.com/i/DBClYq"><img src="https://s3.ax1x.com/2020/11/26/DBClYq.md.png" alt="DBClYq.md.png"></a></p>
<h2 id="格式规范"><a href="#格式规范" class="headerlink" title="格式规范"></a>格式规范</h2><p><strong>1.不能用float，要用double</strong></p>
<p><strong>2.输出的时候不能多输空格</strong></p>
<p>解决long long的定义</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br></pre></td></tr></table></figure>



<p>交换宏的定义</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">#define swap(a,b) &#123;int temp=a;a=b;b=temp&#125;</span><br></pre></td></tr></table></figure>

<p>识别2002&#x2F;11&#x2F;22</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%d/%d/%d&quot;</span>, &amp;y, &amp;m, &amp;d) != EOF</span><br></pre></td></tr></table></figure>



<p>不间断输入</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%lf&quot;</span>,&amp;r) != EOF)</span><br></pre></td></tr></table></figure>



<p>不间断输入之<strong>输入0时程序停止</strong></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(<span class="built_in">scanf</span>(“%d”, &amp;n) &amp;&amp; n)</span><br></pre></td></tr></table></figure>



<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(cin&gt;&gt;n &amp;&amp; n)</span><br></pre></td></tr></table></figure>



<p>好像scanf本身就能整行输入，不间断输入</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%lf&quot;</span>,&amp;r))</span><br></pre></td></tr></table></figure>



<p>取整数位</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n = <span class="number">123456</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> unitPlace = n / <span class="number">1</span> % <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> tenPlace = n / <span class="number">10</span> % <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> hundredPlace = n / <span class="number">100</span> % <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> thousandPlace = n / <span class="number">1000</span> % <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;个位bai:%d\n十位:%d\n百位:%d\n千位:%d\n&quot;</span>, unitPlace, tenPlace, hundredPlace, thousandPlace);</span><br></pre></td></tr></table></figure>



<p>数组定义不能用变量！</p>
<p>输入两行</p>
<p>只要第一个循环EOF，后面的输入在循环里就可以了</p>
<p>\b不是退格</p>
<p>以一定排序规则排序指定范围内的元素，但是算法不具有稳定性，如果元素的值是相同的话不保证它们的相对顺序保持不变</p>
<p>？？？</p>
<p>第二重循环时j</p>
<p>第三重循环时k</p>
<p>答案用ans命名</p>
<p>实际用不到do……while</p>
<p>给定次数以后就不要用</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span>(t--)</span><br></pre></td></tr></table></figure>



<p>使用这种方法代替sqrt()</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i*i&lt;=x;i++)</span><br></pre></td></tr></table></figure>

<p>等号不能少</p>
<p>数组初始化</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">memset</span>(N,<span class="number">0</span>,<span class="keyword">sizeof</span>(N));</span><br></pre></td></tr></table></figure>



<h2 id="复杂度计算"><a href="#复杂度计算" class="headerlink" title="复杂度计算"></a>复杂度计算</h2><h3 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h3><p>1.常数量级，用常熟1</p>
<p>2.保留时间函数的最高项</p>
<p>循环N次，O（n）</p>
<p>3.如果最高项存在，省去最高结项前面的系数</p>
<p>两次N循环，就是O(n)</p>
<p>二次内</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">j*=j</span><br></pre></td></tr></table></figure>

<p>o(n*sqrt())</p>
<h2 id="3-STL和基本数据结构"><a href="#3-STL和基本数据结构" class="headerlink" title="3 STL和基本数据结构"></a>3 STL和基本数据结构</h2><h3 id="3-1-容器"><a href="#3-1-容器" class="headerlink" title="3.1 容器"></a>3.1 容器</h3><h4 id="迭代器"><a href="#迭代器" class="headerlink" title="迭代器"></a>迭代器</h4><p><a target="_blank" rel="noopener external nofollow noreferrer" href="http://c.biancheng.net/view/338.html">http://c.biancheng.net/view/338.html</a></p>
<p>使用前先进行声明</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;<span class="type">int</span>&gt;::iterator i;</span><br></pre></td></tr></table></figure>





<p>迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围</p>
<p>设计人员无需关心容器对象的内存分配的实现细节</p>
<p>但是，迭代器不仅仅是指针，因此你不能认为<strong>他们一定具有地址值</strong>。例如，一个数组索引，也可以认为是一种迭代器</p>
<p>案例:遍历vector</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="comment">//i是指针！！！</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    vector&lt;<span class="type">int</span>&gt; v;  <span class="comment">//v是存放int类型变量的可变长数组，开始时没有元素</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> n = <span class="number">0</span>; n&lt;<span class="number">5</span>; ++n)</span><br><span class="line">        v.<span class="built_in">push_back</span>(n);  <span class="comment">//push_back成员函数在vector容器尾部添加一个元素</span></span><br><span class="line">    vector&lt;<span class="type">int</span>&gt;::iterator i;  <span class="comment">//定义正向迭代器</span></span><br><span class="line">    <span class="keyword">for</span> (i = v.<span class="built_in">begin</span>(); i != v.<span class="built_in">end</span>(); ++i) &#123;  <span class="comment">//用迭代器遍历容器</span></span><br><span class="line">        cout &lt;&lt; *i &lt;&lt; <span class="string">&quot; &quot;</span>;  <span class="comment">//*i 就是迭代器i指向的元素</span></span><br><span class="line">        *i *= <span class="number">2</span>;  <span class="comment">//每个元素变为原来的2倍</span></span><br><span class="line">    &#125;</span><br><span class="line">    cout &lt;&lt; endl;</span><br><span class="line">    <span class="comment">//用反向迭代器遍历容器</span></span><br><span class="line">    <span class="keyword">for</span> (vector&lt;<span class="type">int</span>&gt;::reverse_iterator j = v.<span class="built_in">rbegin</span>(); j != v.<span class="built_in">rend</span>(); ++j)</span><br><span class="line">        cout &lt;&lt; *j &lt;&lt; <span class="string">&quot; &quot;</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">for(it=shop.begin();it!=shop.end();it++)</span><br></pre></td></tr></table></figure>

<p>常用迭代查找</p>
<h4 id="algorithm"><a href="#algorithm" class="headerlink" title="algorithm"></a>algorithm</h4><h5 id="sort"><a href="#sort" class="headerlink" title="sort()"></a>sort()</h5><p>一般是两个参数</p>
<p>cmp是比较函数</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> a[]=&#123;<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>&#125;;</span><br><span class="line"><span class="built_in">sort</span>(a,a+<span class="number">5</span>,cmp);</span><br></pre></td></tr></table></figure>

<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">sort(toy,toy+1,cmp)</span><br></pre></td></tr></table></figure>

<p>这样做，是自己和自己比较，<strong>易犯错误</strong></p>
<p>结构提比较</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">x</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> a,b,c;</span><br><span class="line">&#125;toy[<span class="number">50</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">cmp</span><span class="params">(x aa,x bb)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> aa.b&gt;bb.b;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="built_in">sort</span>(toy,toy+<span class="number">50</span>,cmp)</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h5 id="reverse"><a href="#reverse" class="headerlink" title="reverse()"></a>reverse()</h5><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">reverse(a.begin(),a.end());</span><br></pre></td></tr></table></figure>

<p>可用于回文数</p>
<h4 id="vector"><a href="#vector" class="headerlink" title="vector"></a>vector</h4><p>向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。</p>
<p>其实原来根本就没这个必要，但是编译器不认</p>
<p> 1.顺序序列</p>
<p>顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。</p>
<p>2.动态数组</p>
<p>支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加&#x2F;删除元素的操作。</p>
<p>3.能够感知内存分配器的（Allocator-aware）</p>
<p>容器使用一个内存分配器对象来动态地处理它的存储需求。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    vector&lt;<span class="type">int</span>&gt;a;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">10</span>;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        a.<span class="built_in">push_back</span>(i);</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;a.<span class="built_in">size</span>()&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">10</span>;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        cout&lt;&lt;a[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h4 id="queue"><a href="#queue" class="headerlink" title="queue"></a>queue</h4><p>a.pop() 是void</p>
<p><strong>总结：</strong>先进先出；push到队尾；pop队首元素。</p>
<p>注意，不是双向队列</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    queue&lt;<span class="type">int</span>&gt;a;</span><br><span class="line">    a.<span class="built_in">push</span>(<span class="number">1000</span>);</span><br><span class="line">    a.<span class="built_in">push</span>(<span class="number">200</span>);</span><br><span class="line">    cout&lt;&lt;a.<span class="built_in">front</span>()&lt;&lt;endl;</span><br><span class="line">    cout&lt;&lt;a.<span class="built_in">back</span>()&lt;&lt;endl;</span><br><span class="line">    a.<span class="built_in">pop</span>();</span><br><span class="line">    cout&lt;&lt;a.<span class="built_in">size</span>()&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p> 这东西不是双向的</p>
<p>swap需要开 c11</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span>       <span class="comment">// std::cout</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span>          <span class="comment">// std::queue</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span> <span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  queue&lt;<span class="type">int</span>&gt; foo,bar;</span><br><span class="line">  foo.<span class="built_in">push</span> (<span class="number">10</span>); foo.<span class="built_in">push</span>(<span class="number">20</span>); foo.<span class="built_in">push</span>(<span class="number">30</span>);</span><br><span class="line">  bar.<span class="built_in">push</span> (<span class="number">111</span>); bar.<span class="built_in">push</span>(<span class="number">222</span>);</span><br><span class="line"></span><br><span class="line">  foo.<span class="built_in">swap</span>(bar);</span><br><span class="line"></span><br><span class="line">  std::cout &lt;&lt; <span class="string">&quot;size of foo: &quot;</span> &lt;&lt; foo.<span class="built_in">size</span>() &lt;&lt; <span class="string">&#x27;\n&#x27;</span>;</span><br><span class="line">  std::cout &lt;&lt; <span class="string">&quot;size of bar: &quot;</span> &lt;&lt; bar.<span class="built_in">size</span>() &lt;&lt; <span class="string">&#x27;\n&#x27;</span>;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h4 id="list"><a href="#list" class="headerlink" title="list"></a>list</h4><p>list就是数据结构中的双向链表</p>
<h4 id="deque"><a href="#deque" class="headerlink" title="deque"></a><strong>deque</strong></h4><p>double-ended queue</p>
<p>这好像才是双向队列</p>
<p>ush_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">x</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> a,b,c;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">cmp</span><span class="params">(x aa,x bb)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> aa.b&gt;bb.b;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  string a;</span><br><span class="line">  a=<span class="string">&quot;Hello World&quot;</span>;</span><br><span class="line">  cout &lt;&lt; a &lt;&lt; endl;</span><br><span class="line">  cout &lt;&lt; a.<span class="built_in">size</span>() &lt;&lt; endl;</span><br><span class="line">  cout &lt;&lt; a[<span class="number">3</span>] &lt;&lt; endl;</span><br><span class="line">  <span class="built_in">reverse</span>(a.<span class="built_in">begin</span>(),a.<span class="built_in">end</span>());</span><br><span class="line">  cout &lt;&lt; a &lt;&lt; endl;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h4 id="string"><a href="#string" class="headerlink" title="string"></a>string</h4><h3 id="3-1-1-vector"><a href="#3-1-1-vector" class="headerlink" title="3.1.1 vector"></a>3.1.1 vector</h3><p>vector是STL的动态数组</p>
<p>可以以数组的方式遍历</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    cin&gt;&gt;n;</span><br><span class="line">    <span class="keyword">while</span>(n--)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> n1,l;</span><br><span class="line">        cin&gt;&gt;n1;</span><br><span class="line">        vector&lt;<span class="type">int</span>&gt;p;</span><br><span class="line">        cin&gt;&gt;l;</span><br><span class="line">        p.<span class="built_in">push_back</span>(l);</span><br><span class="line">        cin&gt;&gt;l;</span><br><span class="line">        p.<span class="built_in">push_back</span>(l);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n1;i++)</span><br><span class="line">            cout &lt;&lt; p[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="3-1-2-栈和stack"><a href="#3-1-2-栈和stack" class="headerlink" title="3.1.2 栈和stack"></a>3.1.2 栈和stack</h3><p>栈是经典的先进后出FILO</p>
<p>HDU1062（这道题还可以用string和reverse实现）</p>
<p>The underlying container may be any of the standard container class  templates or some other specifically designed container class. The  container shall support the following operations:</p>
<ul>
<li>empty</li>
<li>size</li>
<li>back</li>
<li>push_back</li>
<li>pop_back</li>
</ul>
<h3 id="3-1-3-队列和queue"><a href="#3-1-3-队列和queue" class="headerlink" title="3.1.3 队列和queue"></a>3.1.3 队列和queue</h3><p>队列是经典的先进先出FIFO</p>
<p>HDU1702</p>
<p>The underlying container may be one of the standard container class  template or some other specifically designed container class. This  underlying container shall support at least the following operations:</p>
<ul>
<li>empty</li>
<li>size</li>
<li>front</li>
<li>back</li>
<li>push_back</li>
<li>pop_front</li>
</ul>
<p> The standard container classes <a target="_blank" rel="noopener external nofollow noreferrer" href="http://www.cplusplus.com/deque">deque</a> and <a target="_blank" rel="noopener external nofollow noreferrer" href="http://www.cplusplus.com/list">list</a> fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container <a target="_blank" rel="noopener external nofollow noreferrer" href="http://www.cplusplus.com/deque">deque</a> is used.</p>
<h3 id="3-1-4-优先队列和priority-queue"><a href="#3-1-4-优先队列和priority-queue" class="headerlink" title="3.1.4 优先队列和priority_queue"></a>3.1.4 优先队列和priority_queue</h3><h3 id="3-1-5-链表和list"><a href="#3-1-5-链表和list" class="headerlink" title="3.1.5 链表和list"></a>3.1.5 链表和list</h3><p>链表的插入和删除都是常数时间，主要应对插入删除频繁的问题</p>
<p>HDU1276</p>
<p>初始化方案</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            mylist.<span class="built_in">push_back</span>(i);</span><br><span class="line">        &#125;</span><br></pre></td></tr></table></figure>

<p>遍历方案为迭代器</p>
<p>迭代器本质是指针</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(it = mylist.begin();it != mylist.end();it++)</span><br></pre></td></tr></table></figure>

<p>STL已经完善了很多操作，比如清空，删除节点，反转，排序，访问第一个和最后一个元素，删除相邻重复元素</p>
<p>有点像队列，但本质完全不同</p>
<p>没说结构体？应该差不多？</p>
<h3 id="3-1-6-set"><a href="#3-1-6-set" class="headerlink" title="3.1.6 set"></a>3.1.6 set</h3><p>hdu2094</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    set&lt;string&gt;A,B;</span><br><span class="line">    string s1,s2;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    <span class="keyword">while</span>(cin&gt;&gt;n &amp;&amp; n)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            cin&gt;&gt;s1&gt;&gt;s2;</span><br><span class="line">            A.<span class="built_in">insert</span>(s1);</span><br><span class="line">            A.<span class="built_in">insert</span>(s2);</span><br><span class="line">            B.<span class="built_in">insert</span>(s2);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(A.<span class="built_in">size</span>()-B.<span class="built_in">size</span>()==<span class="number">1</span>)</span><br><span class="line">            cout&lt;&lt;<span class="string">&quot;Yes&quot;</span>&lt;&lt;endl;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            cout&lt;&lt;<span class="string">&quot;NO&quot;</span>&lt;&lt;endl;</span><br><span class="line">        A.<span class="built_in">clear</span>();</span><br><span class="line">        B.<span class="built_in">clear</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">A.size()</span><br></pre></td></tr></table></figure>

<p>这个最好用</p>
<p>set用法+unique用法，unique，去重，但不是真正去重，而是把重复的放在后面返回重复第一个下标，如果没记错的话，还不知道unique去重原理问度娘</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">set&lt;string&gt;se;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    string s;</span><br><span class="line">    cin&gt;&gt;n;</span><br><span class="line">    <span class="keyword">while</span>(n--)</span><br><span class="line">    &#123;</span><br><span class="line">        cin&gt;&gt;s;</span><br><span class="line">        <span class="built_in">sort</span>(s.<span class="built_in">begin</span>(),s.<span class="built_in">end</span>());</span><br><span class="line">        s.<span class="built_in">erase</span>(<span class="built_in">unique</span>(s.<span class="built_in">begin</span>(),s.<span class="built_in">end</span>()),s.<span class="built_in">end</span>());</span><br><span class="line">        se.<span class="built_in">insert</span>(s);</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;se.<span class="built_in">size</span>();</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>数组全部遍历</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (it=A.<span class="built_in">begin</span>(); it!=A.<span class="built_in">end</span>(); ++it)</span><br><span class="line">    &#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&#x27; &#x27;</span> &lt;&lt; *it;</span><br><span class="line">        cout &lt;&lt; <span class="string">&#x27;\n&#x27;</span>;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>我觉得A.find有问题，这个留待后续研究</p>
<p>查找元素是否存在</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">A.<span class="built_in">insert</span>(<span class="number">5</span>);</span><br><span class="line">   A.<span class="built_in">insert</span>(<span class="number">4</span>);</span><br><span class="line">   A.<span class="built_in">insert</span>(<span class="number">5</span>);</span><br><span class="line">   <span class="keyword">if</span>( *A.<span class="built_in">find</span>(<span class="number">4</span>) ==<span class="number">4</span> ) cout&lt;&lt;<span class="string">&quot;True&quot;</span>&lt;&lt;endl;</span><br><span class="line">   A.<span class="built_in">erase</span>(<span class="number">4</span>);</span><br><span class="line">   <span class="keyword">if</span>( *A.<span class="built_in">find</span>(<span class="number">4</span>) ==<span class="number">4</span> ) cout&lt;&lt;<span class="string">&quot;True&quot;</span>&lt;&lt;endl;</span><br><span class="line">   <span class="keyword">else</span> cout&lt;&lt;<span class="string">&quot;False&quot;</span>&lt;&lt;endl;</span><br></pre></td></tr></table></figure>

<p>想要插入元素需要借助中间变量</p>
<p>集合的内部是可以比较输出的</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="keyword">auto</span> it = ++A.<span class="built_in">cbegin</span>(); it != A.<span class="built_in">cend</span>(); it++)</span><br><span class="line">        &#123;</span><br><span class="line">            cout &lt;&lt; <span class="string">&quot; &quot;</span> &lt;&lt; *it;</span><br><span class="line">        &#125;</span><br><span class="line">        cout&lt;&lt;endl;</span><br></pre></td></tr></table></figure>

<p>更多详细内容</p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/u012604810/article/details/79804928">https://blog.csdn.net/u012604810/article/details/79804928</a></p>
<h3 id="3-1-7-map"><a href="#3-1-7-map" class="headerlink" title="3.1.7  map"></a>3.1.7  map</h3><p>map使用平衡二叉搜索树实现高速查找</p>
<h3 id="3-1-8-next-permutation"><a href="#3-1-8-next-permutation" class="headerlink" title="3.1.8 next_permutation"></a>3.1.8 next_permutation</h3><p>按照字典序进行排列，cba的字典序大于abc</p>
<p><strong>只能针对字符使用</strong></p>
<p>实现一串字符的<strong>全排列</strong>的当前排列的<strong>下一个排列</strong></p>
<p>字典序大小比较：从第一个字符开始一个一个比较，然后找到到一个不相等的，哪个大，哪个字典序就大，如果找不到不相等的，那就相等</p>
<p>HDU1027</p>
<p>从后往前找一个Si&lt;Si+1，然后从i+1到n之间找一个比Si大的最小字符，交换位置，然后把i+1到n升序排序</p>
<p>该函数，在下一个排列存在的情况下返回while，不存在的情况返回false</p>
<h3 id="排序算法"><a href="#排序算法" class="headerlink" title="排序算法"></a>排序算法</h3><h4 id="冒泡算法"><a href="#冒泡算法" class="headerlink" title="冒泡算法"></a>冒泡算法</h4><p>通过n-1趟排序，将大的数一步一步往上冒</p>
<p>O（n^2）</p>
<h5 id="Flag思想"><a href="#Flag思想" class="headerlink" title="Flag思想"></a>Flag思想</h5><p>观察函数swap是否被调用</p>
<p>如果没有发生排序，则false</p>
<p>如果flag为false，说明已排完</p>
<p>这个优化方案好像不错</p>
<h4 id="qsort"><a href="#qsort" class="headerlink" title="qsort()"></a>qsort()</h4><p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://www.cnblogs.com/tsingke/p/5347672.html">https://www.cnblogs.com/tsingke/p/5347672.html</a></p>
<p>见C语言笔记</p>
<h4 id="不打乱顺序的情况下，找出最小"><a href="#不打乱顺序的情况下，找出最小" class="headerlink" title="不打乱顺序的情况下，找出最小"></a>不打乱顺序的情况下，找出最小</h4><p>遍历</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;n;i++)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span>(temp1 &gt; d[i])</span><br><span class="line">    &#123;</span><br><span class="line">        temp1=d[i];</span><br><span class="line">        temp2=i;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>就没更好的方案？</p>
<p>上课时提到了一种方案</p>
<p>直接摆擂台，大数和小数各一个，通过遍历实现，最大最小的序号用变量记住，</p>
<p>（如果是两个相关联的量）正确做法是构建结构体，选择<strong>结构题内容</strong>经行结构体排序（排序才需要这么做）</p>
<h2 id="4-搜索技术"><a href="#4-搜索技术" class="headerlink" title="4 搜索技术"></a>4 搜索技术</h2><h3 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h3><p>二分查找真的很简单吗？并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：</p>
<p>Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… </p>
<p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://www.zhihu.com/question/36132386/answer/712269942">https://www.zhihu.com/question/36132386/answer/712269942</a></p>
<p>首先先<strong>排序</strong></p>
<p>核心是<strong>查找</strong>！！！！</p>
<p>然后每次缩小一半范围</p>
<p>O(log2n)</p>
<p>二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找<strong>要求线性表必须采用顺序存储结构</strong>，而且表中元素按关键字有序排列</p>
<h3 id="4-1-递归和排列"><a href="#4-1-递归和排列" class="headerlink" title="4.1 递归和排列"></a>4.1 递归和排列</h3><p>排列与组合</p>
<p>用next_permutation轻易实现全排列</p>
<p>使用递推方程讲解递归概念</p>
<p>计算机中，递归是用嵌套实现的，涉及指针，地址，栈的使用</p>
<h3 id="4-2-子集生成和组合问题"><a href="#4-2-子集生成和组合问题" class="headerlink" title="4.2 子集生成和组合问题"></a>4.2 子集生成和组合问题</h3><p>一个包含N个元素的集合，它的子集有2的n次方个</p>
<h3 id="4-3-BFS（广度优先）"><a href="#4-3-BFS（广度优先）" class="headerlink" title="4.3 BFS（广度优先）"></a>4.3 BFS（广度优先）</h3><p>题目，概念太多，未完待续</p>
<h3 id="4-4-DFS（深度优先）"><a href="#4-4-DFS（深度优先）" class="headerlink" title="4.4 DFS（深度优先）"></a>4.4 DFS（深度优先）</h3><h4 id="4-4-2-回溯和剪枝"><a href="#4-4-2-回溯和剪枝" class="headerlink" title="4.4.2 回溯和剪枝"></a>4.4.2 回溯和剪枝</h4><h3 id="4-5-小结"><a href="#4-5-小结" class="headerlink" title="4.5 小结"></a>4.5 小结</h3><p>DFS一般用递归实现，代码比BFS更短</p>
<p>1、如果是求最短路径，树的直径（两次bfs），一般用bfs<br> 2、如果只是左转或者右转（像上一篇博客一样的话）就用dfs<br> 3、如果是翻转系列的（flip game，行列变换）一定是dfs</p>
<h2 id="5-高级数据结构"><a href="#5-高级数据结构" class="headerlink" title="5 高级数据结构"></a>5 高级数据结构</h2><p>数据结构的作用是<strong>分析数据，组织数据，存储数据</strong></p>
<p>（1）存储的空间效率</p>
<p>地图与棋盘就是典型的图，前者更加复杂，用1表示相邻，用0表示不相邻</p>
<p>(2)访问的效率</p>
<p>存储无序数字，很明显在排序过后再二分查找效率最高</p>
<p>数据结构有三要素</p>
<p>（1）逻辑结构：线性结构，非线性结构，集合，图</p>
<p>（2）存储结构：顺序存储，链式存储，索引存储，散列存储</p>
<p>（3）数据的运算：初始化，判空，统计，查找，插入，删除，更新（？）</p>
<h3 id="5-1-并查集"><a href="#5-1-并查集" class="headerlink" title="5.1 并查集"></a>5.1 并查集</h3><p>HUD1213</p>
<p>代码附上</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1050</span>;</span><br><span class="line"><span class="type">int</span> s[maxn];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init_set</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;maxn;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        s[i]=i;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">find_set_old</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x==s[x]?x:<span class="built_in">find_set</span>(s[x]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">find_set</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x==s[x]?x:<span class="built_in">find_set</span>(s[x]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">union_set</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    x = <span class="built_in">find_set</span>(x);</span><br><span class="line">    y = <span class="built_in">find_set</span>(y);</span><br><span class="line">    <span class="keyword">if</span>(x!=y) s[x]=s[y];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t,n,m,x,y;</span><br><span class="line">    cin &gt;&gt; t;</span><br><span class="line">    <span class="keyword">while</span>(t--)</span><br><span class="line">    &#123;</span><br><span class="line">        cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">        <span class="built_in">init_set</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=m;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            cin&gt;&gt;x&gt;&gt;y;</span><br><span class="line">            <span class="built_in">union_set</span>(x,y);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(s[i]==i) ans++;<span class="comment">//只要数组下标与元素相同，就属于一个集合</span></span><br><span class="line">        &#125;</span><br><span class="line">        cout&lt;&lt;ans&lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>其中，查找和合并还可以继续优化，复杂度从O(n)降到O(log2n)</p>
<h4 id="5-1-2-合并的优化"><a href="#5-1-2-合并的优化" class="headerlink" title="5.1.2 合并的优化"></a>5.1.2 合并的优化</h4><p>合并时先搜根结点,依据数的高度决定合并方向，即小树向大树靠拢</p>
<p>（所以这是一种单项关系）</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn=<span class="number">1050</span>;</span><br><span class="line"><span class="type">int</span> s[maxn];</span><br><span class="line"><span class="type">int</span> height[maxn];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">init_set</span><span class="params">()</span><span class="comment">//初始化，学到了</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;maxn;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        s[i]=i;</span><br><span class="line">        height[i]=i;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">find_set</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> x==s[x]?x:<span class="built_in">find_set</span>(s[x]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">union_set</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    x = <span class="built_in">find_set</span>(x);</span><br><span class="line">    y = <span class="built_in">find_set</span>(y);</span><br><span class="line">    <span class="keyword">if</span>(height[x]==height[y])</span><br><span class="line">    &#123;</span><br><span class="line">        height[x]+=<span class="number">1</span>;</span><br><span class="line">        s[y]=x;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(height[x]&lt;height[y]) s[x]=y;</span><br><span class="line">        <span class="keyword">else</span> s[y]=x;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> t,n,m,x,y;</span><br><span class="line">    <span class="comment">//cin &gt;&gt; t;</span></span><br><span class="line">    t=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(t--)</span><br><span class="line">    &#123;</span><br><span class="line">        cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">        <span class="built_in">init_set</span>();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=m;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            cin&gt;&gt;x&gt;&gt;y;</span><br><span class="line">            <span class="built_in">union_set</span>(x,y);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(s[i]==i) ans++;<span class="comment">//只要数组下标与元素相同，就属于一个集合</span></span><br><span class="line">        &#125;</span><br><span class="line">        cout&lt;&lt;ans&lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="5-1-3-查询的优化——路径压缩"><a href="#5-1-3-查询的优化——路径压缩" class="headerlink" title="5.1.3 查询的优化——路径压缩"></a>5.1.3 查询的优化——路径压缩</h4><p>好家伙，直接把树长变为1</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">find_set</span><span class="params">(<span class="type">int</span> x)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span>(x!=s[x]) s[x]=find_set(s[x]);</span><br><span class="line">    <span class="keyword">return</span> s[x];<span class="comment">//递归写法</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如果怕爆栈，多设几个变量走循环</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">find_set</span><span class="params">(<span class="type">int</span> x)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> r=x;</span><br><span class="line">    <span class="keyword">while</span>(s[r]!=r)r=s[r];</span><br><span class="line">    <span class="type">int</span> i=x,j;</span><br><span class="line">    <span class="keyword">while</span>(i!=r)</span><br><span class="line">    &#123;</span><br><span class="line">        j=s[i];</span><br><span class="line">        s[i]=r;</span><br><span class="line">        i=j;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> r;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>这两种优化产生的优势在HDU1312均没有体现</p>
<h3 id="5-2-二叉树"><a href="#5-2-二叉树" class="headerlink" title="5.2 二叉树"></a>5.2 二叉树</h3><p>书是非线性结构，书本的目录就是典型的树形结构</p>
<p>A binary tree is a finite set of vertices that is either empty or  consists of a root r and two disjoint binary trees called the left and  right subtrees. There are three most important ways in which the  vertices of a binary tree can be systematically traversed or ordered.  They are preorder, inorder and postorder.</p>
<h4 id="5-2-1-二叉树的存储"><a href="#5-2-1-二叉树的存储" class="headerlink" title="5.2.1 二叉树的存储"></a>5.2.1 二叉树的存储</h4><h5 id="1-二叉树的性质"><a href="#1-二叉树的性质" class="headerlink" title="1 二叉树的性质"></a>1 二叉树的性质</h5><p>二叉树的每个节点最多有两个子节点</p>
<p>如果每一层节点数都是满的，称之为<strong>满二叉树</strong></p>
<p>如果满二叉树只在最后一层缺失，且缺失编号都在后边，称之为<strong>完全二叉树</strong></p>
<h5 id="2-二叉树的存储结构"><a href="#2-二叉树的存储结构" class="headerlink" title="2 二叉树的存储结构"></a>2 二叉树的存储结构</h5><p>一般用指针实现</p>
<p>结构体里有一个节点的值，有两个指针指向左右节点</p>
<h4 id="5-2-2-二叉树的遍历"><a href="#5-2-2-二叉树的遍历" class="headerlink" title="5.2.2 二叉树的遍历"></a>5.2.2 二叉树的遍历</h4><h5 id="1-宽度优先遍历"><a href="#1-宽度优先遍历" class="headerlink" title="1 宽度优先遍历"></a>1 宽度优先遍历</h5><h5 id="2-深度优先遍历"><a href="#2-深度优先遍历" class="headerlink" title="2 深度优先遍历"></a>2 深度优先遍历</h5><p>默认左儿子在右儿子前面</p>
<p>分为<strong>先序遍历，中序遍历，后序遍历</strong>三种遍历情况</p>
<p>只要中序遍历加上任何一序，就能确定一棵树</p>
<p>前序遍历：父节点-&gt;左儿子-&gt;右儿子</p>
<p>中序遍历(inorder)：左儿子-&gt;父节点-&gt;右儿子</p>
<p>在二叉搜索树中，中序遍历实现了排序功能</p>
<p>后序遍历:   左儿子-&gt;右儿子&gt;父节点</p>
<p>HDU1710为案例讲述</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N=<span class="number">1010</span>;</span><br><span class="line"><span class="type">int</span> pre[N],in[N],post[N];</span><br><span class="line"><span class="type">int</span> k;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">node</span>&#123;</span><br><span class="line">    <span class="type">int</span> value;</span><br><span class="line">    node *l,*r;</span><br><span class="line">    <span class="built_in">node</span>(<span class="type">int</span> value =<span class="number">0</span>,node *l = <span class="literal">NULL</span>,node *r = <span class="literal">NULL</span>):<span class="built_in">value</span>(value),<span class="built_in">l</span>(l),<span class="built_in">r</span>(r)&#123;&#125; <span class="comment">//？？？</span></span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">buildtree</span><span class="params">(<span class="type">int</span> l,<span class="type">int</span> r,<span class="type">int</span> &amp;t,node* &amp;root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> flag=<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=l;i&lt;=r;i++)</span><br><span class="line">        <span class="keyword">if</span>(in[i]==pre[t])</span><br><span class="line">        &#123;</span><br><span class="line">        flag=i;<span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="keyword">if</span>(flag==<span class="number">-1</span>)<span class="keyword">return</span>;</span><br><span class="line">    root=<span class="keyword">new</span> <span class="built_in">node</span>(in[flag]);</span><br><span class="line">    t++;</span><br><span class="line">    <span class="keyword">if</span>(flag&gt;<span class="number">1</span>) <span class="built_in">buildtree</span>(l,flag<span class="number">-1</span>,t,root-&gt;l);</span><br><span class="line">    <span class="keyword">if</span>(flag&lt;r) <span class="built_in">buildtree</span>(flag+<span class="number">1</span>,r,t,root-&gt;r);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">preorder</span><span class="params">(node *root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root != <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        post[k++] = root-&gt;value;</span><br><span class="line">        <span class="built_in">preorder</span>(root-&gt;l);</span><br><span class="line">        <span class="built_in">preorder</span>(root-&gt;r);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">inorder</span><span class="params">(node *root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root!=<span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">inorder</span>(root-&gt;l);</span><br><span class="line">        post[k++] = root-&gt;value;</span><br><span class="line">        <span class="built_in">inorder</span>(root-&gt;r);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">postorder</span><span class="params">(node *root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root!=<span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">postorder</span>(root-&gt;l);</span><br><span class="line">        <span class="built_in">postorder</span>(root-&gt;r);</span><br><span class="line">        post[k++]=root-&gt;value;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">remove_tree</span><span class="params">(node *root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root==<span class="literal">NULL</span>)<span class="keyword">return</span>;</span><br><span class="line">    <span class="built_in">remove_tree</span>(root-&gt;l);</span><br><span class="line">    <span class="built_in">remove_tree</span>(root-&gt;r);</span><br><span class="line">    <span class="keyword">delete</span> root;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n)!=EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;pre[i]);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">1</span>;j&lt;=n;j++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;in[j]);</span><br><span class="line">        node *root;</span><br><span class="line">        <span class="type">int</span> t=<span class="number">1</span>;</span><br><span class="line">        <span class="built_in">buildtree</span>(<span class="number">1</span>,n,t,root);</span><br><span class="line">        k=<span class="number">0</span>;</span><br><span class="line">        <span class="built_in">postorder</span>(root);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;k;i++)<span class="built_in">printf</span>(<span class="string">&quot;%d%c&quot;</span>,post[i],i==k<span class="number">-1</span>?<span class="string">&#x27;\n&#x27;</span>:<span class="string">&#x27; &#x27;</span>);</span><br><span class="line">        <span class="built_in">remove_tree</span>(root);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>（尚未理解）</p>
<h4 id="5-2-3-二叉搜索树"><a href="#5-2-3-二叉搜索树" class="headerlink" title="5.2.3 二叉搜索树"></a>5.2.3 二叉搜索树</h4><p>结构精巧，访问高效</p>
<p>二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： <strong>若它的左子树不空</strong>，则左子树上所有结点的值均小于它的根结点的值； <strong>若它的右子树不空</strong>，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。</p>
<p>（1）建树和插入</p>
<p>（2）删除</p>
<p>（4）遍历</p>
<p>BST的优劣在于它是否为一个平衡的二叉树</p>
<h4 id="5-2-4-treap树"><a href="#5-2-4-treap树" class="headerlink" title="5.2.4 treap树"></a>5.2.4 treap树</h4><p>一种比较简单的平衡二叉搜索树，可翻译成树堆</p>
<p><strong>Treap（树堆）的大部分功能STL的set都可以实现，但因为set的过度封装使得某些特定的功能不能实现，比如求第k大的值</strong></p>
<p>（这时候的代码量已经到80行以上，上课摸不了了）</p>
<h2 id="6-基础算法"><a href="#6-基础算法" class="headerlink" title="6 基础算法"></a>6 基础算法</h2><h3 id="6-1-贪心法"><a href="#6-1-贪心法" class="headerlink" title="6.1 贪心法"></a>6.1 贪心法</h3><p>例题有HDU 2570</p>
<p>把整个问题分成多个步骤，每个步骤都选取当前步骤的最优方案</p>
<p>（就是当赌狗，赌其中一个方面最大）</p>
<h2 id="8-数学"><a href="#8-数学" class="headerlink" title="8 数学"></a>8 数学</h2><h3 id="错排"><a href="#错排" class="headerlink" title="错排"></a>错排</h3><p>错排的递推算法</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">错排的递推公式：f(n) = ( f(n-1) + f(n-2) ) * (n-1)</span><br></pre></td></tr></table></figure>





<h4 id="8-2-数论"><a href="#8-2-数论" class="headerlink" title="8.2 数论"></a>8.2 数论</h4><h4 id="8-2-1-模运算"><a href="#8-2-1-模运算" class="headerlink" title="8.2.1 模运算"></a>8.2.1 模运算</h4><p>将大数变小</p>
<h4 id="8-2-2-快速幂"><a href="#8-2-2-快速幂" class="headerlink" title="8.2.2 快速幂"></a>8.2.2 快速幂</h4><p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://blog.csdn.net/qq_19782019/article/details/85621386">https://blog.csdn.net/qq_19782019/article/details/85621386</a></p>
<p>杭电OJ中序号为2035</p>
<p>机器运算10的9次方，而这个数10的12次方</p>
<p>我们程序设计语言中最大的long lnog类型也无法承载这么大的数值</p>
<p><strong>题目才不会要求你输出结果，因为结果可能会非常的大</strong></p>
<p>(a * b) % p &#x3D; (a % p * b % p) % p</p>
<p>根据上面这条运算法则，可以经行<strong>初步优化</strong>，OJ结果可通过</p>
<p>快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高</p>
<p>指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变</p>
<h4 id="8-2-3-GCD-LCM"><a href="#8-2-3-GCD-LCM" class="headerlink" title="8.2.3 GCD,LCM"></a>8.2.3 GCD,LCM</h4><p>GCD 最小公约数</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span>       </span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">gcd</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> b==<span class="number">0</span>?a:<span class="built_in">gcd</span>(b,a%b);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">lcm</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a*b/<span class="built_in">gcd</span>(a,b);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span> <span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    cout&lt;&lt;<span class="built_in">gcd</span>(<span class="number">120</span>,<span class="number">9</span>)&lt;&lt;<span class="string">&quot; &quot;</span>&lt;&lt;<span class="built_in">lcm</span>(<span class="number">120</span>,<span class="number">9</span>)&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>辗转相除，简单又方便</p>
<h2 id="基础算法思想"><a href="#基础算法思想" class="headerlink" title="基础算法思想"></a>基础算法思想</h2><h3 id="贪婪法"><a href="#贪婪法" class="headerlink" title="贪婪法"></a>贪婪法</h3><p>B独木舟</p>
<p>线上小的，与大的匹配</p>
<h3 id="简单博弈"><a href="#简单博弈" class="headerlink" title="简单博弈"></a>简单博弈</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">F - 石子博弈</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    雄雄学长和正曦学长今天都很无聊。两个人相约一起玩游戏。</span><br><span class="line"></span><br><span class="line">    雄雄学长取出了一堆奇形怪状的石子，并且把它分成了三堆。他和正曦学长轮流从里面取石子，取出最后一颗石子的人胜利。正曦学长觉得这样没意思，于是他要求加入一个限制条件：每个人每次只能取出 1 , 3 , 7 或 9 颗石子。石子数目不够的时候不能多取，如还剩 2 颗石子的情况下，只能拿走 1 颗，而不能选择 3 , 7 , 9 。雄雄学长答应了，但是他要让正曦学长先拿。</span><br><span class="line"></span><br><span class="line">    已知雄雄学长和正曦学长都足够聪明，总是会做出最好的拿石子办法。现在你能知道，正曦学长究竟能不能赢吗？</span><br><span class="line">    输入格式</span><br><span class="line"></span><br><span class="line">    共一行，包括三个整数 n , m 和 k ( 1 ≤ n , m , k ≤ 1000 )，代表三堆石子的数目。</span><br><span class="line">    输出格式</span><br><span class="line"></span><br><span class="line">    如果花椰妹能赢，则输出&quot;win&quot;；否则则输出&quot;lose&quot;。</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>奇 偶 偶 win</p>
<p>奇 奇 偶 win</p>
<h2 id="前缀和差分"><a href="#前缀和差分" class="headerlink" title="前缀和差分"></a>前缀和差分</h2><p>一维前缀和：</p>
<p> 是一个数组的某项下标之前(包括此项元素)的所有数组元素的和</p>
<p> sum[i] &#x3D; a[i] + a[i-1] + …………+ a [2] + a[1]</p>
<p>差分：</p>
<p> 差分是一个数组相邻两元素的差</p>
<p> a[i]  &#x3D;  sum[i]  - sum[i+1]</p>
<p>二维前缀和：</p>
<p> （二维数组）</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">b[x][y] = b[x-1][y] + b[x][y-1] – b[x-1][y-1]+a[x][y]</span><br></pre></td></tr></table></figure>





</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="https://www.mocusez.site">MocusEZ</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://www.mocusez.site/posts/6db3.html">https://www.mocusez.site/posts/6db3.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc/4.0" rel="external nofollow noreferrer" target="_blank">CC BY-NC 4.0</a> 许可协议。转载请注明来自 <a href="https://www.mocusez.site" target="_blank">Mox的笔记库</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"></div><div class="post_share"><div class="social-share" data-image="https://ss0.bdstatic.com/70cFvHSh_Q1YnxGkpoWK1HF6hhy/it/u=4088345299,2353129269&amp;fm=26&amp;gp=0.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/79b6.html"><img class="prev-cover" src="https://cdn.fuhao321.com/uploads/2009/1-200Z20S45cM.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">汇编语言笔记</div></div></a></div><div class="next-post pull-right"><a href="/posts/1ec2.html"><img class="next-cover" src="https://ss3.bdstatic.com/70cFv8Sh_Q1YnxGkpoWK1HF6hhy/it/u=372474886,775763543&amp;fm=26&amp;gp=0.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Python学习笔记</div></div></a></div></nav><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/img/head.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">MocusEZ</div><div class="author-info__description">探索未曾设想的道路</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">61</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">0</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">8</div></a></div><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/mocusez" rel="external nofollow noreferrer" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:285918468@qq.com" rel="external nofollow noreferrer" target="_blank" title="Email"><i class="fas fa-envelope"></i></a><a class="social-icon" href="/atom.xml" target="_blank" title="RSS"><i class="fas fa-rss"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">迎接新的明天</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%8E%AF%E5%A2%83%E9%85%8D%E7%BD%AE"><span class="toc-number">1.</span> <span class="toc-text">环境配置</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%BC%E5%BC%8F%E8%A7%84%E8%8C%83"><span class="toc-number">2.</span> <span class="toc-text">格式规范</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E8%AE%A1%E7%AE%97"><span class="toc-number">3.</span> <span class="toc-text">复杂度计算</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">3.1.</span> <span class="toc-text">时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-STL%E5%92%8C%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">4.</span> <span class="toc-text">3 STL和基本数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-%E5%AE%B9%E5%99%A8"><span class="toc-number">4.1.</span> <span class="toc-text">3.1 容器</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%BF%AD%E4%BB%A3%E5%99%A8"><span class="toc-number">4.1.1.</span> <span class="toc-text">迭代器</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#algorithm"><span class="toc-number">4.1.2.</span> <span class="toc-text">algorithm</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#sort"><span class="toc-number">4.1.2.1.</span> <span class="toc-text">sort()</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#reverse"><span class="toc-number">4.1.2.2.</span> <span class="toc-text">reverse()</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#vector"><span class="toc-number">4.1.3.</span> <span class="toc-text">vector</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#queue"><span class="toc-number">4.1.4.</span> <span class="toc-text">queue</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#list"><span class="toc-number">4.1.5.</span> <span class="toc-text">list</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#deque"><span class="toc-number">4.1.6.</span> <span class="toc-text">deque</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#string"><span class="toc-number">4.1.7.</span> <span class="toc-text">string</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-1-vector"><span class="toc-number">4.2.</span> <span class="toc-text">3.1.1 vector</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-2-%E6%A0%88%E5%92%8Cstack"><span class="toc-number">4.3.</span> <span class="toc-text">3.1.2 栈和stack</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-3-%E9%98%9F%E5%88%97%E5%92%8Cqueue"><span class="toc-number">4.4.</span> <span class="toc-text">3.1.3 队列和queue</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-4-%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E5%92%8Cpriority-queue"><span class="toc-number">4.5.</span> <span class="toc-text">3.1.4 优先队列和priority_queue</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-5-%E9%93%BE%E8%A1%A8%E5%92%8Clist"><span class="toc-number">4.6.</span> <span class="toc-text">3.1.5 链表和list</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-6-set"><span class="toc-number">4.7.</span> <span class="toc-text">3.1.6 set</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-7-map"><span class="toc-number">4.8.</span> <span class="toc-text">3.1.7  map</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-8-next-permutation"><span class="toc-number">4.9.</span> <span class="toc-text">3.1.8 next_permutation</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95"><span class="toc-number">4.10.</span> <span class="toc-text">排序算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%86%92%E6%B3%A1%E7%AE%97%E6%B3%95"><span class="toc-number">4.10.1.</span> <span class="toc-text">冒泡算法</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#Flag%E6%80%9D%E6%83%B3"><span class="toc-number">4.10.1.1.</span> <span class="toc-text">Flag思想</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#qsort"><span class="toc-number">4.10.2.</span> <span class="toc-text">qsort()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8D%E6%89%93%E4%B9%B1%E9%A1%BA%E5%BA%8F%E7%9A%84%E6%83%85%E5%86%B5%E4%B8%8B%EF%BC%8C%E6%89%BE%E5%87%BA%E6%9C%80%E5%B0%8F"><span class="toc-number">4.10.3.</span> <span class="toc-text">不打乱顺序的情况下，找出最小</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-%E6%90%9C%E7%B4%A2%E6%8A%80%E6%9C%AF"><span class="toc-number">5.</span> <span class="toc-text">4 搜索技术</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="toc-number">5.1.</span> <span class="toc-text">二分查找</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-1-%E9%80%92%E5%BD%92%E5%92%8C%E6%8E%92%E5%88%97"><span class="toc-number">5.2.</span> <span class="toc-text">4.1 递归和排列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-2-%E5%AD%90%E9%9B%86%E7%94%9F%E6%88%90%E5%92%8C%E7%BB%84%E5%90%88%E9%97%AE%E9%A2%98"><span class="toc-number">5.3.</span> <span class="toc-text">4.2 子集生成和组合问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-3-BFS%EF%BC%88%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%EF%BC%89"><span class="toc-number">5.4.</span> <span class="toc-text">4.3 BFS（广度优先）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-4-DFS%EF%BC%88%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%EF%BC%89"><span class="toc-number">5.5.</span> <span class="toc-text">4.4 DFS（深度优先）</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#4-4-2-%E5%9B%9E%E6%BA%AF%E5%92%8C%E5%89%AA%E6%9E%9D"><span class="toc-number">5.5.1.</span> <span class="toc-text">4.4.2 回溯和剪枝</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-5-%E5%B0%8F%E7%BB%93"><span class="toc-number">5.6.</span> <span class="toc-text">4.5 小结</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-%E9%AB%98%E7%BA%A7%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">6.</span> <span class="toc-text">5 高级数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#5-1-%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="toc-number">6.1.</span> <span class="toc-text">5.1 并查集</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#5-1-2-%E5%90%88%E5%B9%B6%E7%9A%84%E4%BC%98%E5%8C%96"><span class="toc-number">6.1.1.</span> <span class="toc-text">5.1.2 合并的优化</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-1-3-%E6%9F%A5%E8%AF%A2%E7%9A%84%E4%BC%98%E5%8C%96%E2%80%94%E2%80%94%E8%B7%AF%E5%BE%84%E5%8E%8B%E7%BC%A9"><span class="toc-number">6.1.2.</span> <span class="toc-text">5.1.3 查询的优化——路径压缩</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-2-%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">6.2.</span> <span class="toc-text">5.2 二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#5-2-1-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8"><span class="toc-number">6.2.1.</span> <span class="toc-text">5.2.1 二叉树的存储</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#1-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8"><span class="toc-number">6.2.1.1.</span> <span class="toc-text">1 二叉树的性质</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="toc-number">6.2.1.2.</span> <span class="toc-text">2 二叉树的存储结构</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-2-2-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86"><span class="toc-number">6.2.2.</span> <span class="toc-text">5.2.2 二叉树的遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#1-%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-number">6.2.2.1.</span> <span class="toc-text">1 宽度优先遍历</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-number">6.2.2.2.</span> <span class="toc-text">2 深度优先遍历</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-2-3-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-number">6.2.3.</span> <span class="toc-text">5.2.3 二叉搜索树</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-2-4-treap%E6%A0%91"><span class="toc-number">6.2.4.</span> <span class="toc-text">5.2.4 treap树</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95"><span class="toc-number">7.</span> <span class="toc-text">6 基础算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#6-1-%E8%B4%AA%E5%BF%83%E6%B3%95"><span class="toc-number">7.1.</span> <span class="toc-text">6.1 贪心法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#8-%E6%95%B0%E5%AD%A6"><span class="toc-number">8.</span> <span class="toc-text">8 数学</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%94%99%E6%8E%92"><span class="toc-number">8.1.</span> <span class="toc-text">错排</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#8-2-%E6%95%B0%E8%AE%BA"><span class="toc-number">8.1.1.</span> <span class="toc-text">8.2 数论</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#8-2-1-%E6%A8%A1%E8%BF%90%E7%AE%97"><span class="toc-number">8.1.2.</span> <span class="toc-text">8.2.1 模运算</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#8-2-2-%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="toc-number">8.1.3.</span> <span class="toc-text">8.2.2 快速幂</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#8-2-3-GCD-LCM"><span class="toc-number">8.1.4.</span> <span class="toc-text">8.2.3 GCD,LCM</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3"><span class="toc-number">9.</span> <span class="toc-text">基础算法思想</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B4%AA%E5%A9%AA%E6%B3%95"><span class="toc-number">9.1.</span> <span class="toc-text">贪婪法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%80%E5%8D%95%E5%8D%9A%E5%BC%88"><span class="toc-number">9.2.</span> <span class="toc-text">简单博弈</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E5%92%8C%E5%B7%AE%E5%88%86"><span class="toc-number">10.</span> <span class="toc-text">前缀和差分</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/posts/3e9f.html" title="RMM观察与初探"><img src="https://z1.ax1x.com/2023/10/21/piF47TA.md.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="RMM观察与初探"/></a><div class="content"><a class="title" href="/posts/3e9f.html" title="RMM观察与初探">RMM观察与初探</a><time datetime="2023-10-21T04:30:00.000Z" title="发表于 2023-10-21 12:30:00">2023-10-21</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/5e44.html" title="计算机网络课设——UDP/TCP/TLS Socket实验"><img src="https://s1.ax1x.com/2023/09/09/pP6qXOU.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="计算机网络课设——UDP/TCP/TLS Socket实验"/></a><div class="content"><a class="title" href="/posts/5e44.html" title="计算机网络课设——UDP/TCP/TLS Socket实验">计算机网络课设——UDP/TCP/TLS Socket实验</a><time datetime="2023-09-09T07:10:00.000Z" title="发表于 2023-09-09 15:10:00">2023-09-09</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/cd44.html" title="JQuery的XSS初探"><img src="https://s1.ax1x.com/2023/09/08/pPyvO0O.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="JQuery的XSS初探"/></a><div class="content"><a class="title" href="/posts/cd44.html" title="JQuery的XSS初探">JQuery的XSS初探</a><time datetime="2023-09-08T04:30:00.000Z" title="发表于 2023-09-08 12:30:00">2023-09-08</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/5862.html" title="生产实习记录"><img src="https://s1.ax1x.com/2023/09/02/pPBH058.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="生产实习记录"/></a><div class="content"><a class="title" href="/posts/5862.html" title="生产实习记录">生产实习记录</a><time datetime="2023-09-02T13:51:00.000Z" title="发表于 2023-09-02 21:51:00">2023-09-02</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9a9b.html" title="Fedora-CoreOS配置与试用（2023年）"><img src="https://s1.ax1x.com/2023/08/28/pPa8tlF.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Fedora-CoreOS配置与试用（2023年）"/></a><div class="content"><a class="title" href="/posts/9a9b.html" title="Fedora-CoreOS配置与试用（2023年）">Fedora-CoreOS配置与试用（2023年）</a><time datetime="2023-08-28T11:35:00.000Z" title="发表于 2023-08-28 19:35:00">2023-08-28</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2019 - 2023 By MocusEZ</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener external nofollow noreferrer" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener external nofollow noreferrer" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text"><a href="http://beian.miit.gov.cn/" rel="external nofollow noreferrer"  style="color:#f72b07" target="_blank">闽ICP备2021003009号</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.min.js"></script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>function loadWaline () {
  function insertCSS () {
    const link = document.createElement("link")
    link.rel = "stylesheet"
    link.href = "https://cdn.jsdelivr.net/npm/@waline/client/dist/waline.min.css"
    document.head.appendChild(link)
  }

  function initWaline () {
    const waline = Waline.init(Object.assign({
      el: '#waline-wrap',
      serverURL: 'https://waline.mocusez.site',
      pageview: ,
      dark: 'html[data-theme="dark"]',
      path: window.location.pathname,
      comment: false,
    }, null))
  }

  if (typeof Waline === 'function') initWaline()
  else {
    insertCSS()
    getScript('https://cdn.jsdelivr.net/npm/@waline/client/dist/waline.min.js').then(initWaline)
  }
}

if ('Waline' === 'Waline' || !false) {
  if (false) btf.loadComment(document.getElementById('waline-wrap'),loadWaline)
  else setTimeout(loadWaline, 0)
} else {
  function loadOtherComment () {
    loadWaline()
  }
}</script></div><script>(function(i,s,o,g,r,a,m){i["DaoVoiceObject"]=r;i[r]=i[r]||function(){(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;a.charset="utf-8";m.parentNode.insertBefore(a,m)})(window,document,"script",('https:' == document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/1df8ba05.js","daovoice")
</script><script>var isChatBtn = false
daovoice('init', {
  app_id: '1df8ba05',},{
  launcher: { 
     disableLauncherIcon: isChatBtn // 悬浮 ICON 是否显示
  },
});
daovoice('update');

if (isChatBtn) {
  var chatBtnFn = () => {
    var chatBtn = document.getElementById("chat_btn")
    chatBtn.addEventListener("click", function(){
      daovoice('show')
    });
  }
  chatBtnFn()
} else {
  if (false) {
    function chatBtnHide () {
      daovoice('update', {},{
        launcher: { 
        disableLauncherIcon: true // 悬浮 ICON 是否显示
        },
      });
    }
    function chatBtnShow () {
      daovoice('update', {},{
        launcher: { 
        disableLauncherIcon: false // 悬浮 ICON 是否显示
        },
      });
    }
  }
}</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>